﻿//1482. 制作 m 束花所需的最少天数
//给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
//现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
//花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
//请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 - 1 。


class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k)
    {
        int n = bloomDay.size();
        auto check = [&](int t)->bool
        {
            int sum = 0, num = 0;
            for (int i = 0; i < n && num < m; i++)
            {
                if (bloomDay[i] <= t)
                {
                    sum++;
                    if (sum == k)
                    {
                        num++;
                        sum = 0;
                    }
                }
                else
                {
                    sum = 0;
                }
            }
            return num >= m;
        };

        int left = 1, right = ranges::max(bloomDay);
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (check(mid))
                right = mid - 1;
            else
                left = mid + 1;
        }
        if (check(right + 1))
            return right + 1;
        return -1;
    }
};